package com.xigua._递归;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。
 * 求所有子数组的和的最大值。要求时间复杂度为O(n)。
 * @date 2022/3/1011:55
 */
public class _剑指Offer42_连续子数组的最大和 {

    public static void main(String[] args) {
        System.out.println(maxSubArray1(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }

    public static int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = pre >= 0 ? pre+x : x;
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }

    public static int maxSubArray1(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int sum = 0;
        int min = 0;
        for (int i = 0; i < nums.length; i++) {
            sum +=nums[i];
            ans = Math.max(ans,sum-min);
            min = Math.min(min,sum);
        }
        return ans;
    }



}
